//
// Created by hujizhe on 22/2/2024.
//

#ifndef LEETCODE_BACKTRACE_H
#define LEETCODE_BACKTRACE_H

#include <vector>
#include <functional>
#include <string>
#include <map>
#include "numeric"

using namespace std;

//! 77. 组合
vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> vec(k);

    std::function<void(int, int, vector<vector<int>>&)> func = [&func](int n, int k, vector<vector<int>>& res){
        if(res[0].size() == k) return ;
        vector<vector<int>> cur_res;
        for (int i=0; i< res.size(); i++) {
            vector<int> cur_vec = res[i];
            for(int j=res[i].back() + 1; j<=n; j++) {
                cur_vec.push_back(j);
                cur_res.push_back(cur_vec);
                //回溯
                cur_vec = res[i];
            }
        }
        res = cur_res;
        func(n, k, res);
    };

    for(int i=1; i<n; i++) {
        res.push_back(vector<int>(1, i));
    }
    if (k == 1) {
        res.push_back(vector<int>(1, n));
        return res;
    }
    func(n, k, res);
    return res;
}

//! 216. 组合总和 III
vector<vector<int>> combinationSum3(int k, int n) {
    function<void(int, int, vector<vector<int>>&)> func = [&func](int k, int n, vector<vector<int>>& res) {
        if(res[0].size() == k) {
            vector<vector<int>> cur_res;
            for(int i=0; i<res.size(); i++) {
                if(res[i].back() <= 9) {
                    cur_res.push_back(res[i]);
                }
            }
            res = cur_res;
            return;
        }
        vector<vector<int>> cur_res;
        for (int i=0; i<res.size(); i++) {
            vector<int> cur_vec(res[i].begin(), res[i].end() - 1);
            int prev;
            if(cur_vec.empty()) {
                prev = 1;
            } else {
                prev = cur_vec.back() + 1;
            }
            int last = res[i].back() - prev;
            while(prev < last) {
                cur_vec.push_back(prev);
                cur_vec.push_back(last);
                cur_res.push_back(cur_vec);
                cur_vec.pop_back();
                cur_vec.pop_back();
                prev++;
                last--;
            }
        }
        res = cur_res;
        func(k, n, res);
    };

    vector<vector<int>> res;
    if((k * (1+k)) / 2 > n) return res;
    if((k * (19-k)) / 2 < n) return res;
    res.push_back(vector<int>(1,n));
    func(k, n, res);
    return res;
}

//! 17.电话号码的字母组合
vector<string> letterCombinations(string digits) {
    vector<string> res;
    if(digits.empty()) return res;

    vector<string> dig_vec;
    dig_vec.push_back("abc");
    dig_vec.push_back("def");
    dig_vec.push_back("ghi");
    dig_vec.push_back("jkl");
    dig_vec.push_back("mno");
    dig_vec.push_back("pqrs");
    dig_vec.push_back("tuv");
    dig_vec.push_back("wxyz");

    for (auto str : dig_vec[digits[0] - 50]) {
        res.push_back(string{str});
    }

    for(int i=1; i<digits.size(); i++) {
        vector<string> cur_res;
        for (int j=0; j<res.size(); j++) {
            auto cur_str = res[j];
            for (auto str : dig_vec[digits[i] - 50]) {
                cur_str.push_back(str);
                cur_res.push_back(cur_str);
                cur_str = res[j];
            }
        }
        res = cur_res;
    }

    return res;
}

//! 39.组合总和
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    std::sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    if(candidates.empty()) return res;

    function<void(vector<int>, vector<int>, int, vector<vector<int>>&)> func = [&func](vector<int> candidates, vector<int> cur_vec, int target, vector<vector<int>>& res) {
        int sum = 0;
        for (auto num : cur_vec) {
            sum += num;
        }
        if(sum > target) {
            return;
        } else if(sum == target) {
            res.push_back(cur_vec);
        } else {
            for (int i=0; i<candidates.size(); i++) {
                if (target - sum < candidates[i]) return;
                vector<int> new_vec = cur_vec;
                new_vec.push_back(candidates[i]);
                vector<int> new_candidates(candidates.begin() + i, candidates.end());
                func(new_candidates, new_vec, target, res);
            }
        }
    };
    func(candidates, vector<int>(), target, res);
    return res;
}

//! 40.组合总和II
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    std::sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    if(candidates.empty()) return res;

    function<void(vector<int>, vector<int>, int, vector<vector<int>>&)> func = [&func](vector<int> candidates, vector<int> cur_vec, int target, vector<vector<int>>& res) {
        int sum = 0;
        for (auto num : cur_vec) {
            sum += num;
        }
        if(sum > target) {
            return;
        } else if(sum == target) {
            res.push_back(cur_vec);
        } else {
            for (int i=0; i<candidates.size(); i++) {
                if(i > 0 && candidates[i] == candidates[i-1]) continue;
                if (target - sum < candidates[i]) return;
                vector<int> new_vec = cur_vec;
                new_vec.push_back(candidates[i]);
                vector<int> new_candidates(candidates.begin() + i + 1, candidates.end());
                func(new_candidates, new_vec, target, res);
            }
        }
    };
    func(candidates, vector<int>(), target, res);
    return res;
}

//! 131. 分割回文串
vector<vector<string>> partition(string s) {
    vector<vector<string>> res;

    function<void(string, vector<string>)> func =[&func, &res](string s, vector<string> path) {
        if(s.empty()) {
            res.push_back(path);
        } else {
            int i;
            for (i=s.size() - 1; i>=0; i--) {
                if(s[i] == s[0]) {
                    int prev = 0, last = i;
                    while(prev <= last) {
                        if(s[prev] != s[last]) break;
                        prev++;
                        last--;
                    }
                    if(prev > last) {
                        vector<string> new_path = path;
                        new_path.push_back(s.substr(0, i+1));
                        func(s.substr(i+1, s.size() - i - 1), new_path);
                    }
                }
            }
        }
    };

    func(s, vector<string>());

    return res;
}

//! 93. 复原IP地址
vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    function<void(string s, vector<string> path)> func = [&func, &res](string s, vector<string> path){
        if(path.size() > 4 || (path.size() == 4 && !s.empty())) return;
        if(path.size() == 4 && s.empty()) {
            string str;
            for(int i=0; i<3; i++) {
                str.append(path[i]);
                str.append(".");
            }
            str.append(path[3]);
            res.push_back(str);
        } else {
            if(s.size() < 1) return;
            vector<string> new_path = path;
            new_path.push_back(s.substr(0, 1));
            func(s.substr(1, s.size() - 1), new_path);
            if(s[0] != '0') {
                if(s.size() < 2) return;
                new_path = path;
                new_path.push_back(s.substr(0, 2));
                func(s.substr(2, s.size() - 2), new_path);
                if(s.size() < 3) return;
                if((s[0] - 48) * 100 + (s[1] - 48) * 10 +(s[2] - 48) <= 255) {
                    new_path = path;
                    new_path.push_back(s.substr(0, 3));
                    func(s.substr(3, s.size() - 3), new_path);
                }
            }
        }
    };

    func(s, vector<string>());

    return res;
}

//! 78.子集
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    res.push_back(vector<int>());
    for(int i=0; i<nums.size(); i++) {
        int n = res.size();
        for (int j=0; j<n; j++) {
            vector<int> tmp = res[j];
            tmp.push_back(nums[i]);
            res.push_back(tmp);
        }
    }
    return res;
}

//! 90.子集II
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    res.push_back(vector<int>());
    int count = 0;
    for(int i=0; i<nums.size(); i++) {
        int n = res.size();
        if(i > 0 && (nums[i] == nums[i-1])) {
            count++;
        } else {
            count = 0;
        }
        for (int j=0; j<n; j++) {
            vector<int> tmp = res[j];
            // if(tmp.size() > count || tmp[tmp.size() - count] != nums[i]) continue;
            if(count > 0 && (tmp.size() < count || tmp[tmp.size() - count] != nums[i])) continue;

            tmp.push_back(nums[i]);
            res.push_back(tmp);
        }

    }
    return res;
}


//! 1049. 最后一块石头的重量 II (回溯）
int lastStoneWeightII_(vector<int>& stones) {
    int res = INT_MAX;
    function<void(vector<int>, int)> func = [&func, &res](vector<int> stones, int cur){
        if(stones.empty() && cur < res) {
            res = cur;
            return ;
        }
        for (auto iter = stones.begin(); iter != stones.end(); iter++) {
            vector<int> new_stones(stones.begin(), iter);
            for (auto it = iter + 1; it != stones.end(); it++) {
                new_stones.push_back(*it);
            }
            func(new_stones, abs(cur - *iter));
        }
    };

    func(stones, 0);
    return res;
}

//! 491. 非递减子序列
vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> res;

    function<void(int, vector<int>)> func = [&func, &res, &nums](int idx, vector<int> cur_vec){
        if(cur_vec.size() > 1) res.push_back(cur_vec);
        if(nums.size() == idx) {
            return;
        }
        vector<bool> used(201, false);
        for(int i=idx; i<nums.size(); i++) {
            if(!used[nums[i] + 100] && nums[i] >= cur_vec.back()) {
                used[nums[i] + 100] = true;
                auto tmp = cur_vec;
                tmp.push_back(nums[i]);
                func(i+1, tmp);
            }
        }
    };

    vector<bool> used(201, false);
    for(int i=0; i<nums.size(); i++) {
        if(!used[nums[i] + 100]) {
            used[nums[i] + 100] = true;
            func(i+1, vector<int>(1, nums[i]));
        }
    }

    return res;
}

//! 46.全排列
vector<vector<int>> permute(vector<int>& nums) {

    function<vector<vector<int>>(vector<int>)> func = [&func](vector<int> left_nums){
        if(left_nums.size() == 1) {
            return vector<vector<int>>(1, vector<int>(1, left_nums[0]));
        }
        vector<vector<int>> cur_res;
        auto left_res = func(vector<int>(left_nums.begin() + 1, left_nums.end()));
        for(auto vec : left_res) {
            auto tmp = vec;
            for(int i=0; i<=vec.size(); i++) {
                tmp.insert(tmp.begin() + i, left_nums[0]);
                cur_res.push_back(tmp);
                tmp = vec;
            }
        }
        return cur_res;
    };

    return func(nums);
}


//! 47.全排列II
vector<vector<int>> permuteUnique(vector<int>& nums) {
    function<void(int, vector<int>, vector<int>, vector<vector<int>>&)> Insert = [&Insert](int same_val,vector<int> cur_vec, vector<int> unique, vector<vector<int>>& res){
        if(unique.size() == 0) {
            res.push_back(cur_vec);
            return ;
        }

        int i;

        for(i=cur_vec.size() - 1; i>=0; i--) {
            auto tmp = cur_vec;
            tmp.insert(tmp.begin() + i + 1, unique[0]);
            Insert(same_val, tmp, vector<int>(unique.begin() + 1, unique.end()), res);
            if(cur_vec[i] != same_val) break;
        }

        if(i == -1) {
            auto tmp = cur_vec;
            tmp.insert(tmp.begin(), unique[0]);
            Insert(same_val, tmp, vector<int>(unique.begin() + 1, unique.end()), res);
        }

    };


    function<vector<vector<int>>(vector<int>)> func = [&func, &Insert](vector<int> left_nums){
        if(left_nums.size() == 0) {
            return vector<vector<int>>();
        }
        if(left_nums.size() == 1) {
            return vector<vector<int>>(1, vector<int>(1, left_nums[0]));
        }
        int count = 0;
        sort(left_nums.begin(), left_nums.end());
        while(count < left_nums.size() && left_nums[count] == left_nums[0]) {
            count++;
        }
        vector<vector<int>> cur_res;

        auto left_res = func(vector<int>(left_nums.begin() + count, left_nums.end()));

        if(left_res.empty()) return vector<vector<int>>(1, vector<int>(count, left_nums[0]));

        for(auto vec : left_res) {
            Insert(left_nums[0], vector<int>(count, left_nums[0]), vec, cur_res);
        }

        return cur_res;
    };


    return func(nums);
}

//! 47.全排列II
vector<vector<int>> permuteUnique_(vector<int>& nums) {

    vector<vector<int>> res;
    function<void(vector<int>, vector<bool>)> func = [&func, &nums, &res](vector<int> path, vector<bool> used){
        vector<bool> used_num(21, false);
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++) {
            if(!used[i] && !used_num[nums[i] + 10]) {
                used_num[nums[i] + 10] = true;
                used[i] = true;
                path.push_back(nums[i]);
                func(path, used);
                used[i] = false;
                path.pop_back();
            }
        }
    };

    func(vector<int>(), vector<bool>(nums.size(), false));
    return res;
}

//! 37.解数独
void solveSudoku(vector<vector<char>>& board) {

}
#endif //LEETCODE_BACKTRACE_H
